package mysort

import (
	"math/rand"
	"time"
)

// --------------------------HeapSort------------------------------
// HeapSort 堆排序
func HeapSort(data []int) []int {
	cnt := len(data)
	if cnt < 2 {
		return data
	}

	for i := (cnt - 1) / 2; i >= 0; i-- {
		heapDown(&data, cnt, i)
	}

	for i := cnt - 1; i > 0; i-- {
		data[0], data[i] = data[i], data[0]
		heapDown(&data, i, 0)
	}

	return data
}

func heapDown(heap *[]int, cnt, i int) {
	if cnt < 2 || i < 0 {
		return
	}

	for i < cnt {
		l := 2*i + 1
		if l >= cnt {
			break
		}

		larget := l
		if l+1 < cnt && (*heap)[l] < (*heap)[l+1] {
			larget = l + 1
		}

		if (*heap)[i] > (*heap)[larget] {
			break
		}
		(*heap)[i], (*heap)[larget] = (*heap)[larget], (*heap)[i]
		i = larget
	}
}

// --------------------------HeapSort------------------------------

// --------------------------mergeSort------------------------------
func MergeSort(data *[]int) {
	cnt := len(*data)
	if cnt < 2 {
		return
	}

	// mergeSort(data, 0, len(*data)-1)
	mergeSort2(data)
}

func mergeSort(data *[]int, s, e int) {
	if s == e {
		return
	}
	m := s + ((e - s) >> 1)

	mergeSort(data, s, m)
	mergeSort(data, m+1, e)
	merge(data, s, m, e)
}

func mergeSort2(data *[]int) {
	cnt, mergeSize := len(*data), 1
	for mergeSize < cnt {
		start := 0
		for start < cnt {
			mid := start + mergeSize - 1
			if mid >= cnt-1 {
				break
			}
			end := min(mid+mergeSize, cnt-1)
			merge(data, start, mid, end)
			start = end + 1
		}

		// 防止merge size溢出int最大值
		if mergeSize > cnt>>1 {
			break
		}

		mergeSize <<= 1
	}
}

func merge(data *[]int, s, m, e int) {
	tmp, p1, p2 := []int{}, s, m+1
	for p1 <= m && p2 <= e {
		if (*data)[p1] > (*data)[p2] {
			tmp = append(tmp, (*data)[p2])
			p2++
		} else {
			tmp = append(tmp, (*data)[p1])
			p1++
		}
	}
	for p1 <= m {
		tmp = append(tmp, (*data)[p1])
		p1++
	}
	for p2 <= e {
		tmp = append(tmp, (*data)[p2])
		p2++
	}

	for k, v := range tmp {
		(*data)[s+k] = v
	}
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

// --------------------------mergeSort------------------------------

// --------------------------quickSort------------------------------
func QuickSort(data *[]int) {
	cnt := len(*data)
	if cnt < 2 {
		return
	}

	partionArr(data, 0, cnt-1)
}

func partionArr(data *[]int, s, e int) {
	if s >= e {
		return
	}

	l, r, n := s-1, e+1, (*data)[randInt(s, e)]
	for i := l + 1; i < r; i++ {
		if (*data)[i] < n {
			l++
			(*data)[i], (*data)[l] = (*data)[l], (*data)[i]
		} else if (*data)[i] > n {
			r--
			(*data)[i], (*data)[r] = (*data)[r], (*data)[i]
			i--
		}
	}

	partionArr(data, s, l)
	partionArr(data, r, e)
}

func randInt(min, max int) int {
	if max <= min {
		return 0
	}
	rand.Seed(time.Now().UnixNano())
	return min + rand.Intn(max-min+1)
}

// --------------------------quickSort------------------------------
